#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int maxProfit(int k, vector<int> &prices)
    {
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));
        for (int i = 0; i < 2 * k; i += 2)
        {
            dp[0][i] = -prices[0];
        }
        for (int i = 1; i < (int)prices.size(); i++)
        {
            for (int j = 0; j < 2 * k; j++)
            {
                if (j == 0)
                {
                    dp[i][j] = max(dp[i - 1][j], -prices[i]);
                }
                else if (j % 2 == 0)
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        return dp[prices.size() - 1][2 * k - 1];
    }
};

int main()
{
    vector<int> prices{3, 2, 6, 5, 0, 3};
    Solution sol;
    cout << sol.maxProfit(2, prices) << endl;
    return 0;
}